#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
    int maximumUnits(vector<vector<int>> &boxTypes, int truckSize)
    {
        int boxSize = boxTypes.size();
        int ans = 0;
        sort(boxTypes.begin(), boxTypes.end(), [&](const vector<int> a, const vector<int> b)
             { return a[1] == b[1] ? a[0] < b[0] : a[1] > b[1]; });

        for (size_t i = 0; i < boxSize; i++)
        {
            cout << boxTypes[i][0] << " " << boxTypes[i][1] << endl;

            if (truckSize >= boxTypes[i][0])
            {
                ans += boxTypes[i][0] * boxTypes[i][1];
                truckSize -= boxTypes[i][0];
            }
            else
            {
                ans += truckSize * boxTypes[i][1];
                break;
            }
        }

        return ans;
    }

    int maximumUnits_2(vector<vector<int>> &boxTypes, int truckSize)
    {
        // 按价值排序
        sort(boxTypes.begin(), boxTypes.end(), [](vector<int> &a, vector<int> &b) -> bool
             { return a[1] > b[1]; });
        int remain = truckSize;
        int res = 0;
        for (int i = 0; i < boxTypes.size(); i++)
        {
            // 添加容量小
            int add = min(remain, boxTypes[i][0]);
            res += add * boxTypes[i][1];
            remain -= add;
            if (remain == 0)
                return res;
        }
        return res;
    }

    int maximumUnits_3(vector<vector<int>> &boxTypes, int truckSize)
    {
        sort(boxTypes.begin(), boxTypes.end(), [](const auto &L, const auto &R)
             { return L[1] > R[1]; });
        //箱子容量从大到小排序
        int ans = 0, add = 0;
        for (int i = 0; i < boxTypes.size() && truckSize > 0; i++)
        {
            add = min(truckSize, boxTypes[i][0]);
            truckSize -= add;
            ans += add * boxTypes[i][1];
        }
        return ans;
    }
};
int main()
{
    Solution s;
    vector<vector<int>> boxTypes = {{5, 10}, {2, 5}, {1, 5}, {4, 9}, {3, 9}};
    int truckSize = 10;
    cout << s.maximumUnits_2(boxTypes, truckSize) << endl;
    system("pause");
    return 0;
}
